# -*- coding: utf-8 -*-
"""
Created on Thu Jun 10 12:34:50 2021

@author: 86189
"""
from itertools import combinations

import pandas as pd


class solution:
    def __init__(self, gragh_information, node, OD, OD_reliability, node_reliability, source, target):
        """
        Parameters
        ----------
        gragh_information : 每个节点的邻接点列表集合
            DESCRIPTION.
        node : 节点集合列表
            DESCRIPTION.
        OD : OD对，具体参考表格
            DESCRIPTION.
        OD_reliability : 每条链路的可靠度列表
            DESCRIPTION.
        node_reliability : 节点的可靠度列表
            DESCRIPTION.
        source : 源节点
            DESCRIPTION.
        target : 宿节点
            DESCRIPTION.

        Returns
        -------
        None.

        """
        self.gragh_information = gragh_information
        self.node = node
        self.OD = OD
        self.source = source
        self.target = target
        self.path = [self.source]
        self.select = self.gragh_information[self.node.index(source)]
        self.result = []
        self.convert_result = []
        self.OD_reliability = OD_reliability
        self.node_reliability = node_reliability
        self.realibility = 0

    def backtrack(self):
        """
        函数说明：回溯算法，返回所有路集

        Returns
        -------
        None.

        """
        if self.path[-1] == self.target:
            self.result = self.result + [self.path]
            return
        for value in self.select:
            if value in self.path:
                continue
            self.path = self.path + [value]
            self.select = self.gragh_information[self.node.index(value)]
            self.backtrack()
            self.path = self.path[0:-1]
            self.select = self.gragh_information[self.node.index(self.path[-1])]

    def convert(self):
        """
        函数说明：将所有节点列表表示的路集转化为所有链路标号表示的路集合

        Returns
        -------
        None.

        """
        new_result = []
        for i in range(len(self.result)):
            new_result = new_result + [[]]
        for i in range(len(self.result)):
            for j in range(len(self.result[i]) - 1):
                index = self.OD[(self.OD['Source'] == self.result[i][j]) & (
                        self.OD['Target'] == self.result[i][j + 1])].index.tolist()
                if len(index) == 0:
                    index = self.OD[(self.OD['Source'] == self.result[i][j + 1]) & (
                            self.OD['Target'] == self.result[i][j])].index.tolist()
                new_result[i] = new_result[i] + index
        self.convert_result = new_result

    def calculate_realibilty(self):
        """
        函数说明：容斥原理法计算可靠度

        Returns
        -------
        None.

        """
        path_number = len(self.result)  # 路集合的数目
        sequence = list(range(path_number))
        for i in range(1, path_number + 1):  # 对1-pathnumber进行遍历
            k = (-1) ** (i - 1)
            temp = list(combinations(sequence, i))
            rows = len(temp)
            for j in range(rows):
                self.realibility = self.realibility + k * self.calculate_joinnode(temp[j]) * self.calculate_joinlink(
                    temp[j])

    def calculate_joinnode(self, position):
        """
        函数说明：计算节点的可靠度

        Parameters
        ----------
        position : TYPE
            DESCRIPTION.

        Returns
        -------
        ret : TYPE
            DESCRIPTION.

        """
        path = []
        for i in position:
            path = path + [self.result[i]]
        ret = 1
        join_node = []
        length = len(path)
        if length == 1:
            for i in range(len(path[0])):
                ret = ret * self.node_reliability[self.node.index(path[0][i])]
            return ret
        else:
            for i in range(length):
                join_node = list(set(join_node).union(set(path[i])))
            for i in range(len(join_node)):
                ret = ret * self.node_reliability[self.node.index(join_node[i])]
            return ret

    def calculate_joinlink(self, position):
        """
        函数说明：计算边的可靠度

        Parameters
        ----------
        position : TYPE
            DESCRIPTION.

        Returns
        -------
        ret : TYPE
            DESCRIPTION.

        """
        link_path = []
        for i in position:
            link_path = link_path + [self.convert_result[i]]
        ret = 1
        join_link = []
        length = len(link_path)
        if length == 1:
            for i in range(len(link_path[0])):
                ret = ret * self.OD_reliability[link_path[0][i]]
            return ret
        else:
            for i in range(length):
                join_link = list(set(join_link).union(set(link_path[i])))
            for i in range(len(join_link)):
                ret = ret * self.OD_reliability[join_link[i]]
            return ret


def process(dataframe1, node):
    """
    函数说明：预处理，目的是得到邻接节点列表

    Parameters
    ----------
    dataframe1 : OD对信息表
        DESCRIPTION.
    node : 节点列表
        DESCRIPTION.

    Returns
    -------
    graph_information : 邻接节点列表
        DESCRIPTION.

    """
    graph_information = [[] for i in node]
    for i in range(len(node)):
        temp = dataframe1['Target'][dataframe1['Source'] == node[i]]
        if len(temp.values.tolist()) != 0:
            graph_information[i] = graph_information[i] + temp.values.tolist()
        temp1 = dataframe1['Source'][dataframe1['Target'] == node[i]]
        if len(temp1.values.tolist()) != 0:
            graph_information[i] = graph_information[i] + temp1.values.tolist()
    return graph_information


if __name__ == '__main__':
    dataframe1 = pd.read_excel('OD对.xlsx')
    dataframe2 = pd.read_excel('节点可靠度.xlsx')
    node = dataframe2['节点'].tolist()
    OD = dataframe1.loc[:, ['Source', 'Target']]
    OD_reliability = dataframe1['可靠度'].tolist()
    node_reliability = dataframe2['可靠度'].tolist()
    graph_information = process(dataframe1, node)
    s = solution(graph_information, node, OD, OD_reliability, node_reliability, 'D1', 'S1')
    s.backtrack()
    s.convert()
    s.calculate_realibilty()
    f = s.realibility
    print(f)
